#include "linked_list.h"

ListNode* reverse(ListNode* head) {
#if 1  // 递归方式
  if (head == nullptr || head->next == nullptr) return head;
  ListNode* next = reverse(head->next);
  head->next->next = head;
  head->next = nullptr;
  return next;
#else  // 双指针方式
  if (head == nullptr || head->next == nullptr) return head;
  ListNode* pre = nullptr;
  ListNode* cur = head;
  ListNode* next;
  while (cur) {
    next = cur->next;
    head->next = pre;
    pre = cur;
    cur = next;
  }
  return pre;
#endif
}
// pre,[begin,......,end]
void reverse(ListNode* pre, ListNode* begin, ListNode* end) {
#if 0  // 递归方式

#else  // 双指针方式
  // 头插法
  while (begin != end) {
    pre->next = begin->next;
    begin->next = end->next;
    end->next = begin;
    begin = pre->next;
  }
#endif
}

ListNode* reverse(ListNode* head, int k) {
  ListNode* cur = head;
  int count = 0;
  while (cur && count != k) {
    cur = cur->next;
    count++;
  }
  // 左闭右开区间:[head, cur）为反转区间
  if (count == k) {
    cur = reverse(cur, k);
    while (count) {
      count--;
      ListNode* tmp = head->next;
      head->next = cur;
      cur = head;
      head = tmp;
    }
    head = cur;
  }
  return head;
}